'''
堆是完全二叉树，这里是用了数组实现：
    左节点: i * 2 + 1, 右节点: i * 2 + 2
    父节点: (i - 1) // 2 向下取整使得不管自己是左节点还是右节点都是一个公式
大顶堆，堆顶元素为最大的
在每棵子树上：根都是最大的
'''
from typing import List


def heap_insert(nums, i):
    '''
    插入，只往上看
    :param nums: 维护的堆
    :param i: 在i位置插入元素
    '''
    # note: in python -1//2=-1, 且-1表示访问最后一个元素
    while (parent := (i - 1) // 2) >= 0 and nums[i] > nums[parent]:
        nums[i], nums[parent] = nums[parent], nums[i]
        i = parent

def heapify(nums, i, size):
    '''
    向下调整，只往下看。找子节点中最大的替换，让他来当新子树的根，且循环下去
    :param nums: 维护的堆
    :param i: 在i位置
    :param size: 堆的大小,确保往下看的时候不越界
    '''
    while (l := i * 2 + 1) < size:
        r = l + 1
        best_child = r if (r < size and nums[r] > nums[l]) else l
        best = best_child if nums[best_child] > nums[i] else i
        if best == i:
            break
        nums[i], nums[best] = nums[best], nums[i]
        i = best


class Heap:
    def __init__(self, nums, comparator=lambda x, y: x < y):
        self.nums = list(nums) if nums else []
        self.size = len(self.nums)
        self.comparator = comparator
        for i in range((self.size - 2) // 2, -1, -1):
            self._heapify(i)

    def get_size(self):
        return self.size

    def empty(self):
        return self.size == 0

    def peek(self):
        if self.size == 0:
            return None
        return self.nums[0]

    def pop(self):
        if self.size == 0:
            return None
        nums = self.nums
        nums[0], nums[-1] = nums[-1], nums[0]
        res = nums.pop()
        self.size -= 1
        if self.size > 0:
            self._heapify(0)
        return res

    def push(self, v):
        self.nums.append(v)
        self._heap_insert(self.size)
        self.size += 1

    def pop_push(self, v):
        if self.empty():
            self.push(v)
            return None
        res = self.nums[0]
        self.nums[0] = v
        self._heapify(0)
        return res

    def push_pop(self, v):
        if self.empty() or self.comparator(v, self.nums[0]):
            return v
        res = self.nums[0]
        self.nums[0] = v
        self._heapify(0)
        return res

    def _heap_insert(self, i):
        nums = self.nums
        while (parent := (i - 1) // 2) >= 0 and self.comparator(nums[i], nums[parent]):
            nums[i], nums[parent] = nums[parent], nums[i]
            i = parent

    def _heapify(self, i):
        nums = self.nums
        size = self.size
        while (l := i * 2 + 1) < size:
            r = l + 1
            best = r if (r < size and self.comparator(nums[r], nums[l])) else l
            best = best if self.comparator(nums[best], nums[i]) else i
            if best == i:
                break
            nums[i], nums[best] = nums[best], nums[i]
            i = best

if __name__ == '__main__':
    # 测试代码
    heap = Heap([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
    print(heap.pop())  # 弹出堆顶元素
    heap.push(10)  # 插入元素
    print(heap.get_size())  # 获取堆的大小

    # 使用自定义比较器（例如比较元素的绝对值）
    abs_comparator = lambda x, y: abs(x) < abs(y)
    heap_with_abs = Heap([-3, 100, -4, 1, 5, -9, 2, 6, 5, 3, 5], comparator=abs_comparator)
    print(heap_with_abs.pop())  # 弹出堆顶元素